Namespacing everything to /UVa.
[andmenj-acm.git] / UVa / 11338 - Minefield / #11338.3.cpp#
blob663699de34c607f2f6b5e1300a52aa027867429d
1 #include <iostream>
2 #include <vector>
3 #include <queue>
4 #include <map>
5 #include <cmath>
6 #include <sstream>
7 #include <functional>
9 using namespace std;
11 const double infinity = 1E20;
13 struct point{
14   double x, y;
15   point(double X, double Y){ x = X; y = Y;}
18 map< point, double > dist;
20 bool operator ==(const point &a, const point &b){ return (a.x == b.x && a.y == b.y);}
21 bool operator !=(const point &a, const point &b){ return !(a == b);}
22 bool operator <(const point &a, const point &b){ return (a.x < b.x || (a.x == b.x && a.y < b.y));}
23 //bool operator <(point a, point b){ return (a.dist > b.dist);}
24 double distancia(point a, point b){return hypot(a.y-b.y, a.x-b.x);}
28 bool heapCmp(const point &a,const point &b){
29   return (dist[a] > dist[b]);
33 struct heapCompare : public binary_function<point, point, bool>
35   bool operator()(const point &x, const point &y) const
36   { return dist[x] > dist[y]; }
40 struct grafo{
41   //contiene todos los nodos sueltos
42   vector<point> nodos;
43   //contiene un vector con todos los vecinos para el punto point
44   map< point, vector<point> > vecinos;
46   void insert(point a){
47     if (vecinos.count(a) == 1) return; //Ya insertamos este nodo
48     nodos.push_back(a);
49     vector<point> v;
50     vecinos.insert(make_pair(a, v));
51     //printf("Insertando (%f,%f).\n", a.x, a.y);
52   }
54   void make_vecinos(double maxPath){
55     for (map< point, vector<point> >::iterator it=vecinos.begin(); it!=vecinos.end(); ++it){
56       if (distancia((*it).first, point(0.00, 0.00)) > maxPath){
57         //printf("El punto (%f,%f) es un desastre.\n", (*it).first.x, (*it).first.y);
58         continue;
59       }
60       for (map< point, vector<point> >::iterator jt = it; jt!=vecinos.end(); ++jt){
61         //Insertarlo como vecino en los nodos diferentes a el mismo
62         //printf("  Ensayando (*it).first = (%f,%f)\n", (*it).first.x, (*it).first.y);
63         if ((*it).first != (*jt).first){
64           if ((*jt).first.x - (*it).first.x > 1.5){
65             //printf("Rompiendo con a = (%f,%f) y nodos[i] = (%f,%f)\n", a.x, a.y, (*it).first.x, (*it).first.y);
66             break;
67           }
68           vector<point> adj = vecinos[(*it).first];
69           //Asegurarse de no insertar un vecino repetido
70           //    if (find(adj.begin(), adj.end(), a) == adj.end()){
71           if (distancia((*jt).first, (*it).first) <= 1.5){
72             //printf("Insertando (%f,%f) como vecino de (%f,%f).\n", a.x, a.y, (*it).first.x, (*it).first.y);
73             vecinos[(*it).first].push_back((*jt).first);
74             vecinos[(*jt).first].push_back((*it).first);
75           }
76           //    }
77         }
78       }
79     }
80   }
81   
82   void initialize(){
83     dist.clear();
84     for (int i=0; i<nodos.size(); ++i){
85       dist[nodos[i]] = infinity;
86       if (nodos[i].x == 0.00 && nodos[i].y == 0.00){
87         dist[nodos[i]] = 0.00;
88       }
89     }
90   }
92   /*void relax(point u, point v){
93     if (dist[v] > dist[u] + distancia(u, v)){
94       dist[v] = dist[u] + distancia(u, v);
95     }
96     }*/
98   void dijkstra(const double &maxPath, const point &finalPoint){
99     initialize();
100     
101     //priority_queue<point, vector<point>, heapCompare > q(nodos.begin(), nodos.end());
102     priority_queue<point, vector<point>, heapCompare > q;
103     q.push(point(0.0, 0.0));
104     //vector<point> q(nodos.begin(), nodos.end());
105     //make_heap(q.begin(), q.end(), heapCmp);
106     while (!q.empty()){
107       //point u = q.front();
108       //pop_heap(q.begin(), q.end(), heapCmp); q.pop_back();
109       point u = q.top();
110       q.pop();
111       //printf("Saque (%f,%f) cuya distancia es %f\n", u.x, u.y, dist[u]);
112       if (distancia(point(0.00, 0.00), u) + distancia(u, finalPoint) <= maxPath){
113         for (int i=0; i<vecinos[u].size(); ++i){
114           point v = vecinos[u][i];
115           //printf("  Comparando (%f,%f) con (%f,%f) que estan a %f\n", u.x, u.y, v.x, v.y, distancia(u,v));
116           //printf(" dist[u] es %f, dist[v] es %f\n", dist[u], dist[v]);
117           if (dist[vecinos[u][i]] > (dist[u] + distancia(u,v))){
118             //printf("  Actualizando la distancia de v = (%f,%f)\n", v.x, v.y);
119             dist[vecinos[u][i]] = dist[u] + distancia(u, v);
120             //printf("  Nueva distancia de v: %f\n", dist[v]);
121             q.push(v);
122           }
123         }
124       }
125       //make_heap(q.begin(), q.end(), heapCmp);
126     }
127   }
133 int main(){
134   while (true){
136     string s;
137     for (s = ""; s == ""; getline(cin, s));
138     if (s == "*") break;
141     grafo g;
143     stringstream line;
144     line << s;
146     int w,h;
147     line >> w >> h;
148     g.insert(point((double)w, (double)h));
149     g.insert(point(0.00, 0.00));
150     int noPuntos;
151     cin >> noPuntos;
152     for (int i=0; i<noPuntos; ++i){
153       double x,y;
154       cin >> x >> y;
155       g.insert(point(x,y));
156     }
158   
159     double maximoCamino;
160     cin >> maximoCamino;
162     g.make_vecinos(maximoCamino);
163     //cout << "Termine de insertar todos los nodos.\n";
165     /*printf("Voy a imprimir el grafo de %d nodos:\n", g.nodos.size());
166     for (int i=0; i<g.nodos.size(); ++i){
167       printf("Estos son los vecinos de (%f,%f):\n", g.nodos[i].x, g.nodos[i].y);
168       for (int j=0; j<g.vecinos[g.nodos[i]].size(); ++j){
169         printf("  (%f,%f)\n", g.vecinos[g.nodos[i]][j].x, g.vecinos[g.nodos[i]][j].y);
170       }
171       }*/
173     g.dijkstra(maximoCamino, point((double)w, (double)h));
174     //printf("La distancia minima hasta (%d,%d) es %f.\n", w,h,dist[point((double)w, (double)h)]);
175     if (dist[point((double)w, (double)h)] <= maximoCamino){
176       printf("I am lucky!\n");
177     }else{
178       printf("Boom!\n");
179     }
180    
181   }
182   return 0;